// #include <bits/stdc++.h>
// using namespace std;
// #define yes cout << "YES" << endl
// #define no cout << "NO" << endl
// using ll = long long;
// const int N = 4e5 + 10;
// int pri[N] = {0}, pp, primes[N] = {0};
// bool is_prime_1(int x)
// {
//     for (int i = 2; i < x - 1; i++)
//     {
//         if (x % i == 0)
//             return 0;
//     }
//     return 1;
// }

// bool is_prime_2(int x)
// {
//     int sq = sqrt(x);
//     for (int i = 2; i <= x / i; i++)
//     {
//         if (x % i == 0)
//             return 0;
//     }
//     return 1;
// }

// void solve()
// {
//     // for (int i = 2; i <= N;i++)
//     // {
//     //     if(!pri[i])
//     //     {
//     //         for (int j = 2 * i; j <= N; j += i)
//     //             pri[j] = 1;
//     //     }
//     // }

//     //埃氏筛
//     // for (int i = 2; i <= N/i; i++)
//     // {
//     //     if (!pri[i])
//     //     {
//     //         for (int j = i * i; j <= N; j += i)
//     //             pri[j] = 1;
//     //     }
//     // }

//     for (int i = 2; i <= N; i++)
//     {
//         if (!pri[i])
//         {
//             primes[++pp] = i;
//         }
//         for (int j = 1; j <= pp;j++)
//         {
//             pri[primes[j] * i] = 1;
//             if(i%primes[j]==0)
//                 break;
//         }
//     }
//     for (ll i = 1; i <= pp; i++)
//     {
//         cout << primes[i] << endl;
//     }
// }
#include <iostream>
#include <vector>

using namespace std;
const int N = 6e6 + 10;

vector<int> primes;
bool is_composite[N]; // false 表示是质数

void euler_sieve(int limit)
{
    for (int i = 2; i <= limit; ++i)
    {
        if (!is_composite[i])
            primes.push_back(i);
        for (int j = 0; j < primes.size() && 1LL * i * primes[j] <= limit; ++j)
        {
            is_composite[i * primes[j]] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
}

int main()
{
    int limit = 6000000;
    euler_sieve(limit);

    cout << "Number of primes <= " << limit << ": " << primes.size() << endl;
    cout << "First 10 primes: ";
    for (int i = 0; i < 10; ++i)
    {
        cout << primes[i] << " ";
    }
    cout << endl;
    // int t = 1;
    // cin >> t;
    // while (t--)
    // {
    //     euler_sieve()
    //     //solve();
    // }
    return 0;
}
